//#include <iostream>
//#include<map>
//#include<vector>
//using namespace  std;

//Definition for singly-linked list.
//  struct ListNode {
//      int val;
//      ListNode *next;
//      ListNode(int x) : val(x), next(NULL) {}
// };


//class Solution {
//public:
//    ListNode* reverseList(ListNode* head) {
//        ListNode* new_head = new ListNode(-1);
//
//        while(head)
//        {
//            if(new_head->next==nullptr) {
//                new_head->next=head;
//                head=head->next;
//                new_head->next->next= nullptr;
//            }
//
//            else {
//                ListNode* next = new_head->next;
//                ListNode* now = head;
//                head=head->next;
//                new_head->next=now;
//                now->next=next;
//            }
//
//        }
//        ListNode* ret= new_head->next;
//        delete new_head;
//        return ret;
//    }
//};
//int main() {
//    ListNode d1(1);
//    ListNode d2(2);
//    ListNode d3(3);
//    ListNode d4(4);
//    ListNode d5(5);
//
//    d1.next=&d2;
//    d2.next=&d3;
//    d3.next=&d4;
//    d4.next=&d5;
//
//    Solution a1;
//    a1.reverseList(&d1);
//}

//class Solution {
//
//public:
//    string replaceSpace(string s) {
//        //1.统计空格，计算所需的空间
//        //2.开始从后往前插入
//        int i,count=0;
//        for(i =0;i<s.size();i++)
//        {
//            if(s[i]==' ')
//            {
//                count++;
//            }
//        }
//
//        int old_tail=s.size();
//        int new_tail = s.size()+count*2; // 需要的空间
//
//        s.resize(new_tail);
//        while(old_tail>=0)
//        {
//            //1.遇到空格，替换与没有遇到
//
//            if(s[old_tail]==' ')
//            {
//                s[new_tail--]='0';
//                s[new_tail--]='2';
//                s[new_tail--]='%';
//            }
//            else
//            {
//               s[new_tail--] =s[old_tail];
//            }
//            old_tail--;
//        }
//        return s;
//    }
//};
//
//int main()
//{
//    Solution d1;
//    cout<<d1.replaceSpace(string("We are happy."));
//}
//
//class Solution {
//public:
//    int findRepeatNumber(vector<int>& nums) {
//        map<int,int> result;
//
//        //入数据，如果在入的途中val为2就直接返回
//        for(int i =0;i<nums.size();i++)
//        {
//            auto ret =result.find(nums[i]);
//            if(ret ==result.end())//找不到
//            {
//                result.insert(make_pair(nums[i],1));
//            }
//            else
//            {
//                ret->second++;
//                if(ret->second== 2)
//                {
//                    return ret->first;
//                }
//            }
//        }
//        return 1000000;
//    }
//};
//int main()
//{
//
//}



//class A
//{
//public:
//    A ():m_iVal(0){test();}
//    virtual void func() { std::cout<<m_iVal<<' ';}
//    void test(){func();}
//public:
//    int m_iVal;
//};
//
//class B : public A
//{
//public:
//    B(){test();}
//    virtual void func()
//    {
//        ++m_iVal;
//        std::cout<<m_iVal<<' ';
//    }
//};
//
//int main(int argc ,char* argv[])
//{
//    A*p = new B;
//    p->test();
//    return 0;



//class Solution {
//public:
//    vector<string> topKFrequent(vector<string>& words, int k) {
//
//        map<string,int> save1;
//        //入数据
//        for(auto ch : words)
//        {
//            save1[ch]++;//入数据，没有插入有val++
//        }
//
//        multimap<int,string,greater<int>> save2;
//        for(auto ch: save1)
//        {
//            save2.insert(make_pair(ch.second,ch.first));
//        }
//
//        vector<string> ret;
//
//        int count=0;
//        for(auto ch: save2)
//        {
//
//            if(count++<k)
//            {
//                ret.push_back(ch.second);
//            }
//            else {
//                break;
//            }
//        }
//        return ret;
//    }
//};
//
//int main()
//{
//    vector<string> d1{"i", "love", "leetcode", "i", "love", "coding"};
//    Solution d2;
//    vector<string>ret= d2.topKFrequent(d1,2);
//
//}



//1.统计入数据到map中
//2.multimap进行二次排序
//3.打印

//#include<iostream>
//#include<string>
//#include<vector>
//#include<map>
//using namespace std;

//1.统计入数据到map中
//2.multimap进行二次排序
//3.打印
//
//#include<iostream>
//#include<string>
//#include<vector>
//#include<map>
//using namespace std;
//
//int main()
//{
//    string input,tmp;
//    getline(cin,input);//入一行数据
//    map<string,int> save1;
//
//    //1
//    for(int i =0;i<input.size();i++)
//    {
//
//        if(isalpha(input[i])==true) {
//            if(isalpha(input[i]+32)==true)//大写字符
//            {
//                tmp.push_back(input[i]+32);
//            }
//            else
//            {
//                tmp.push_back(input[i]);
//            }
//        }
//        else { //是·空格的情况
//            save1[tmp]++;
//            tmp.clear();
//        }
//    }
//    //2
//    multimap<int,string,greater<int>> save2;
//    for(auto& ch: save1)
//    {
//        save2.insert(make_pair(ch.second,ch.first));
//    }
//
//
//    //3
//    for(auto& ch : save2)
//    {
//        cout<<ch.second<<":"<<ch.first<<endl;
//    }
//
//    return 0;
//}

//class Solution {
//public:
//    int search(vector<int>& nums, int target) {
//
//        //那就是有序，二分查找
//        int count =0,begin=0,end=nums.size()-1;
//        while(begin<end)//确定数据位置
//        {
//            int middle = (begin+end)/2;
//
//            if(nums[middle] <target)
//            {
//                begin=middle+1;
//            }
//            else if( nums[middle] > target)
//            {
//                end = middle-1;
//            }
//            else {
//                end=middle+1;
//                while(begin<middle && nums[middle]==nums[middle-1])
//                {
//                    count++;
//                    middle--;
//
//                }
//                break;
//            }
//        }
//
//        while(end<nums.size()){
//            if(nums[end]==target)
//            {
//                count++;
//                end++;
//            }
//            else {
//                break;
//            }
//        }
//
//        return count;
//    }
//};
//
//
//
//int main()
//{
//    Solution d1;
//    vector<int> d2{1};
//    cout<<d1.search(d2,1);
//}


//#include<iostream>
//#include<vector>
//#include<algorithm>
//using namespace std;
//
//
//int main()
//{
//    int number;
//    cin>>number;
//
//    vector<unsigned long long> result;
//    result.resize(number*3);//获取人数
//
//    for(auto& ch : result)
//    {
//        cin>>ch;
//    }
//
//    sort(result.begin(),result.end());//排序
//
//    unsigned long long  max=0,index=result.size()-2;
//
//    while(index > 0&&number--)
//    {
//        max += result[index];
//        index-=2;
//    }
//
//    if(max>10)
//    {
//        cout<<10;
//    }
//    else
//    {
//        cout<<max;
//    }
//    return 0;
//}

//#include<iostream>
//#include<string>
//#include<set>
//using namespace std;
//
//
//int main()
//{
//    string str1;
//    string str2;
//    set<char> Delete;
//    getline(cin,str1);
//    getline(cin,str2);
//
//    for(auto& ch : str2) {//入数据
//        Delete.insert(ch);
//    }
//
//    str2.clear();
//    for(auto& ch: str1) {
//        if(Delete.find(ch)==Delete.end()){
//            str2.push_back(ch);
//        }
//    }
//
//    cout<<str2;
//}

//
//#include<iostream>
//#include<string>
//using namespace std;
//
//void Reserve(string & result,int begin,int end)//逆置
//{
//    end--;
//    while(begin<end)
//    {
//        swap(result[begin++],result[end--]);//交换
//    }
//
//
//}
//int main()
//{
//    string result;
//    getline(cin,result);
//
//    Reserve(result,0,result.size());//全体逆
//
//    //部分逆
//    int begin=0,end=0;
//    while(end<=result.size())
//    {
//        if(result[end]==' '||result[end]=='\0')
//        {
//            Reserve(result,begin,end);
//            begin=++end;
//        }
//        else{
//            end++;
//        }
//    }
//
//
//
//    cout<<result;//结果
//    return 0;
//}


//#include<iostream>
//#include<vector>
//using namespace std;
//
//void Juge(int& decide ,int&count,int& index)
//{
//    if(decide>0)
//    {
//        count++;
//        decide=0;
//        index++;
//    }
//}
//int main()
//{
//    //收取
//    int number;
//    cin>>number;
//    vector<int>save;
//    save.resize(number);
//    for(auto &ch:save)
//    {
//        cin>>ch;
//    }
//
//    int index=0,count=0,decide=0;
//
//    while(index<save.size())
//    {
//        while(index<save.size()&&save[index]==save[index+1])//开始就是相等的情况的处理
//        {
//            index++;
//        }
//
//        while(index<save.size()&&save[index]<=save[index+1])//递增的情况
//        {
//            index++;
//            decide++;
//        }
//
//        Juge(decide,count,index);
//
//        while(index<save.size()&&save[index]>=save[index+1])//递增的情况
//        {
//            index++;
//            decide++;
//        }
//        Juge(decide,count,index);
//    }
//
//    cout<<count;
//}


//class Solution {
//public:
//    int MoreThanHalfNum_Solution(vector<int> numbers) {
//
//        int hp = 1, index = 1, number = numbers.front();
//
//
//        while (index < numbers.size()) {
//            if (numbers[index] == number) {
//                hp++;
//            } else {
//                hp--;
//                if (hp == 0)//跟换防御位
//                {
//                    number = numbers[index];
//                    hp=1;
//                }
//            }
//            index++;
//        }
//
//        return number;
//    }
//};

//
//int main()
//{
//        Solution d1;
//       cout<< d1.MoreThanHalfNum_Solution(vector<int>{1,2,3,2,2,2,5,4,2});
//}



//#include<iostream>
//#include<string>
//using namespace std;
//int main()
//{
//    string save,result,end;
//    getline(cin,save);
//
//    int index=0,max=0;
//
//    while(index<save.size())
//    {
//        while(save[index]<49||save[index]>57)//去字符
//        {
//            index++;
//        }
//
//        while(save[index]>=49 && save[index]<=57)
//        {
//            result.push_back(save[index++]);
//        }
//
//        if(result.size()>max)
//        {
//            end.clear();
//            end=result;
//        }
//        result.clear();
//    }
//    cout<<end;
//
//    return 0;
//}


//#include<iostream>
//#include<map>
//#include<set>
//using namespace  std;
//
//int main()
//{
//    //插入
//   set<int> d1;
//   map<int ,int>d2;
//    auto ret1= d1.insert(1);
//    auto ret2=d1.insert(1);
//
//    auto ret3= d2.insert(pair<int,int>(1,1));
//    auto ret4=d2.insert(pair<int,int>(1,1));
//    auto ret5=d2.insert(pair<int,int>(1,2));
//
//
//    cout<<"set"<<endl;
//    cout<<ret1.second<<endl;
//    cout<<ret2.second<<endl;
//    cout<<"--------------------------------------------------"<<endl;
//
//    cout<<"map"<<endl;
//    cout<<ret3.second<<endl;
//    cout<<ret4.second<<endl;
//    cout<<ret5.second<<endl;
//    return 0;
//}

//#include<iostream>
//#include<string>
//#include<algorithm>
//
//using namespace std;
//
//int main()
//{
//    string result;
//    string save("ABCDEFG");//存储
//
//    long M, N;
//    while(cin>>M>>N)
//    {
//        if(M==0)
//        {
//            cout<<0;
//        }
//        while(M)
//        {
//            int tmp=M%N;
//            M/=N;
//
//            if(tmp>9){
//                result.push_back(save[tmp-10]);
//            }
//            else {
//                result.push_back(tmp+48);
//            }
//
//        }
//        reverse(result.begin(),result.end());
//        cout<<result<<endl;
//        result.clear();
//    }
//
//    return 0;
//}
//#include<iostream>
//#include<vector>
//using namespace std;
//
//class Solution {
//public:
//    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
//
//        int end = matrix[0].size()-1;//最后一个元素
//
//        for(int i =0;i<matrix.size();i++)
//        {
//            while(end>=0&&matrix[i][end]>target)
//            {
//                end--;
//            }
//            if(end>=0&&matrix[i][end]==target)
//            {
//                return true;
//            }
//        }
//        return false;
//    }
//};
//
//
//int main()
//{
//    Solution d1;
//    vector<vector<int>>d2;
////    d2.push_back(vector<int>{});
//    d1.findNumberIn2DArray(d2,-10);
//
//    return 0;
//}



//#include<iostream>
//#include<vector>
//using namespace std;
//
//int main()
//{
//    //接收数据
//    vector<int>result;
//    int number;
//    cin>>number;
//    result.resize(number);
//
//    for(auto &ch :result)
//    {
//        cin>>ch;
//    }
//
//    int max=result[0];//数列中或许全部都是负数所以不可以给0
//    //状态转移方程：f(a)=(f(a-1)+f(a))>f(a)?f(a-1)+f(a):f(a)
//    for(int i =1;i<result.size();i++)
//    {
//        result[i]=(result[i-1]+result[i])>result[i]?(result[i-1]+result[i]):result[i];
//        if(result[i]>max)
//        {
//            max=result[i];
//        }
//    }
//    cout<<max;
//    return 0;
//}